BiNode

发表于 | 分类于 |
字数统计: 795 字 | 阅读时长 ≈ 3 分钟

题目描述：二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

注意：本题相对原题稍作改动

示例：
输入： [ 4, 2, 5, 1, 3, null, 6, 0 ]
输出： [ 0, null, 1, null, 2, null, 3, null, 4, null, 5, null, 6 ]

提示：节点数量不会超过 100000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public TreeNode convertBiNode(TreeNode root) {

  }
}

方法一：递归

对二叉搜索树采用中序遍历就能得到一个升序序列，采用修改每一个根节点的左右指向的方式 ，实现了原址修改

image.png 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  TreeNode head = new TreeNode(-1); // 为了返回单向链表的头节点而多设的一个节点
  TreeNode pre = null;              // 指向当前节点的前一个节点
  public TreeNode convertBiNode(TreeNode root) {
    inorder(root);
    return head.right;
  }
  private void inorder(TreeNode node) {
    if(node == null) return;
    inorder(node.left);
    if(pre == null) {      // 第一个节点
      pre = node;       // 记录第一个节点
      head.right = node; // 记录它，它将作为单链表的表头
    } else {               // 第一个节点之后的节点
      pre.right = node;  // 前一个节点的右指针指向当前节点
      pre = node;        // 更新pre指向
    }
    node.left = null;      // 当前节点的左指针设为null
    inorder(node.right);
  }
}

算法分析：

  • 时间复杂度：中序遍历所有节点仅访问一次，所以为O(n)
  • 空间复杂度：递归使用辅助栈空间O(n)，几个临时变量O(1)，因此为O(n)

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：45.4 MB, 在所有 Java 提交中击败了55.21%的用户

方法二：遍历

采用栈的方式中序遍历二叉树，当节点不为空时就入栈，如为空时则表示到到最左节点，就从栈中弹出一个节点，将头节点的right指向次节点，此节点的left置空，头节点右移一个节点，然后遍历右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public TreeNode convertBiNode(TreeNode root) {
    if(root == null) return null;
    TreeNode head = new TreeNode(-1);
    TreeNode pre = null;

    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode node = root;
    while(!stack.isEmpty()|| node != null) {
      if(node != null) {
        stack.push(node);
        node = node.left;
      } 
      else {
        node = stack.pop();
        if(pre == null) {
          pre = node;
          head.right = pre;
        } else {
          pre.right = node;
          pre = node;
        }
        node.left = null;
        node = node.right;
      }
    }
    return head.right;
  }
}

算法分析：

  • 时间复杂度：中序遍历所有节点仅访问一次，所以为O(n)
  • 空间复杂度：此方法空间的消耗取决于栈存储的元素数量，其在最坏情况下会达到 O(n)

执行结果：通过

  • 执行用时：5 ms, 在所有 Java 提交中击败了20.12%的用户
  • 内存消耗：45.7 MB, 在所有 Java 提交中击败了11.31%的用户